package leetcode

import "sort"

// 深度优先搜索 + 剪枝
// 1. 若 nums 和不能被 k 整除，则无法拆分
// 2. 尝试将每个元素添加到不同的桶里面，若最终可以将所有的元素都分配完毕，则表示可以全部拆分掉哦😯
// https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
func canPartitionKSubsets(nums []int, k int) bool {
	sum, s := 0, 0
	for _, v := range nums {
		sum += v
	}
	if (sum % k) != 0 {
		return false
	}
	s = sum / k
	cur := make([]int, k)

	var dfs func(idx int) bool
	dfs = func(idx int) bool {
		if idx == len(nums) {
			return true
		}
		for i := 0; i < k; i++ {
			if i > 0 && cur[i] == cur[i-1] {
				continue
			}
			cur[i] += nums[idx]
			if cur[i] <= s && dfs(idx+1) {
				return true
			}
			cur[i] -= nums[idx]
		}
		return false
	}
	sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] })
	return dfs(0)
}
